from math import sqrt
from itertools import count, cycle

def cfvalues(cf):
    """ Returns the successive partial values of the given continued fraction."""
    n0, d0 = 0, 1
    n1, d1 = 1, 0
    for a in cf:
        n = n0 + a * n1
        d = d0 + a * d1
        n0, n1 = n1, n
        d0, d1 = d1, d
        yield (n,d)

def cfe_gen():
    """ Generates the continued fraction for e."""
    yield 2
    for k in count(1):
        yield 1
        yield 2 * k
        yield 1
        
def cfroot(n):
    """ Returns the continued fraction of the square root of n."""
    nsqr = sqrt(n)
    i = int(nsqr)
    if i == nsqr: return [i]
    a, b = i, 1

    result = [i]
    abseen = set()
    
    while (a, b) not in abseen:
        abseen.add((a, b))
        b = (n - a * a) / b
        i = int((nsqr + a) / b)
        a = i * b - a        
        result.append(i)

    return result

def cfroot_gen(n):
    """ Generates the continued fraction of the square root of n."""
    cfr = cfroot(n)
    yield cfr[0]
    for i in cycle(cfr[1:]):
        yield i
